# 删除链表的倒数第N个结点: https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/


# Definition for singly-linked list.
from typing import List


class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
head = ListNode(val=0, next=ListNode(val=0, next=ListNode(val=0, next=ListNode)))

class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        """
            使用双指针解决问题：快慢指针，是两个指针相隔 n 的距离。 快指针到达末尾时，慢指针刚好是到达倒数n的位置
        """
        # 设立头结点, 一致删除操作（头结点）
        h = ListNode()
        h.next = head

        # 添加快慢指针
        i = 1
        # 初始化，pre指向h， 当只有一个元素时，pre指针也不为None，统一删除逻辑
        fast, lower, pre = head, head, h
        while fast.next:
            # 拉开n的距离
            if i >= n:
                pre = pre.next
                lower = lower.next        

            fast = fast.next
            i += 1
        
        # 执行删除
        pre.next = pre.next.next
        lower.next = None

        return h.next

    

        

